﻿// 0731train04.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

/*
所以他决定从众多心意商品中购买 3 件，而且想尽可能的花完资金，
现在请你设计一个程序帮助小明计算尽可能花费的最大资金额。

输入
第一行为整型数组 M，数组长度小于100，数组元素记录单个商品的价格；
单个商品价格小于1000；
第二行输入为购买资金的额度R，R < 100000。
输出
输出为满足上述条件的最大花费额度
如果不存在满足上述条件的商品请返回-1

输入
23,26,36,27
78

输出
76

输入
23,30,40
26
输出
-1

 */
void solve01(vector<int>&oh_vec, int target)
{
	sort(oh_vec.begin(), oh_vec.end());
	if (oh_vec.size()==3)
	{
		int sum = oh_vec[0] + oh_vec[1] + oh_vec[2];
		if (sum <= target)
		{
			cout << sum;
			return;
		}
		cout << -1;
		return;
	}

	int result = -1;
	int vec_size = oh_vec.size();

	for (int i=0;i<oh_vec.size();i++)
	{
		int curr_num = oh_vec[i];
		int left = i + 1;
		int right = vec_size - 1;

		while (left<right)
		{
			int sum = curr_num + oh_vec[left] + oh_vec[right];
			if (sum==target)
			{
				result = sum;
				break;
			}
			else if (sum<target)
			{
				result = max(sum, result);
				left += 1;
			}
			else if (sum>target)
			{
				right -= 1;
			}
		}

		//for------
	}

	
	cout << result;
	//solve01
}


/*
 三回合跳到最后一格
 索引和最小

 数组中的步数可以重复，但数组中的元素不能重复使用。

输入
1,4,5,2,0,2
9
输出
4,5,0

 */


struct Node
{
	int value, index;
	Node() = default;
	Node(int value, int index) :value(value), index(index) {};
};

bool CompareNodeValue(Node node_a, Node node_b)
{
	if (node_a.value==node_b.value)
	{
		return node_a.index < node_b.index;
	}
	return node_a.value < node_b.value;
}

void solve02(vector<int>&origin_vec, int target)
{
	vector<Node>oh_vec;
	for (int i=0; i<origin_vec.size();i++)
	{
		Node node(origin_vec[i], i);
		oh_vec.push_back(node);
	}

	sort(oh_vec.begin(), oh_vec.end(), CompareNodeValue);

	vector<int>result_vec(3, 0);
	int min_index_count = INT_MAX;
	int vec_size = oh_vec.size();

	for (auto&item:oh_vec)
	{
		cout << item.value << ' ';
	}
	cout << '\n';


	for (int i=0;i<oh_vec.size();i++)
	{
		int left = i+1;
		int right = vec_size - 1;

		if (oh_vec[i].value > target) break;

		while (left<right)
		{
			int sum = oh_vec[i].value + oh_vec[left].value + oh_vec[right].value;
			int index_count = oh_vec[i].index + oh_vec[left].index + oh_vec[right].index;
			if (sum==target)
			{
				if (index_count < min_index_count)
				{
					min_index_count = index_count;
					result_vec[0] = oh_vec[i].index;
					result_vec[1] = oh_vec[left].index;
					result_vec[2] = oh_vec[right].index;
				}
				
				right -= 1;//重要，这里只能写right-=1，如果加上left+=1会漏掉最小索引和
			}
			else if(sum<target)
			{
				left += 1;
			}
			else if (sum>target)
			{
				right -= 1;
			}
			//while-----
		}


		//for------
	}
	sort(result_vec.begin(), result_vec.end());

	for (auto&item:result_vec)
	{
		cout << item << ' ';
	}

	for (int i=0; i<result_vec.size();i++)
	{
		int index = result_vec[i];
		if (i!=result_vec.size()-1)
		{
			cout << origin_vec[index] << ',';
		}
		else
		{
			cout << origin_vec[index];
		}
	}

	//solve02
	//------
}


int main()
{
	{
		//1,4,5,2,0,2
		//9
		//1,5,2,0,2,4
		//9
		//1,3,5,2,0,2,5
		//10
		//3,5,2
		string input;
		getline(cin, input);
		stringstream oh_sstream(input);
		vector<int>oh_vec;
		string token;
		while (getline(oh_sstream, token,','))
		{
			oh_vec.push_back(stoi(token));
		}

		int target;
		cin >> target;
		cout << target;
		for (auto&item:oh_vec)
		{
			cout << item << ' ';
		}

		//vector<int>oh_vec = { 1,3,5,2,0,2,5 };
		//int target = 10;

		solve02(oh_vec, target);

		return 0;
	}


	//23,26,36,27
	//78

	string vec_input;
	getline(cin, vec_input);
	stringstream oh_sstream(vec_input);
	string token;
	vector<int>oh_vec;
	while (getline(oh_sstream, token, ','))
	{
		oh_vec.push_back(stoi(token));
	}

	//for (auto&item:oh_vec)
	//{
	//	cout << item << ' ';
	//}
	string target;
	getline(cin, target);
	
	//vector<int>oh_vec = { 23,26,36,27 };
	//int target = 78;
	solve01(oh_vec, stoi(target));
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
